package SubjectHashTable;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class IsHappy {

/**
 * 难度：简单
 * 
 * 202. 快乐数
 * 	编写一个算法来判断一个数 n 是不是快乐数。
 * 	「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，
 * 	然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果可以
 * 	变为  1，那么这个数就是快乐数。
 * 	如果 n 是快乐数就返回 True ；不是，则返回 False 。
 * 
 * 示例：
 * 	输入：19
 * 	输出：true
 * 	解释：
 * 	1^2 + 9^2 = 82
 * 	8^2 + 2^2 = 68
 * 	6^2 + 8^2 = 100
 * 	1^2 + 0^2 + 0^2 = 1
 *
 * */	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IsHappy ih = new IsHappy();
		System.out.println(ih.isHappy3(19));
	}
	private int getNext(int n) {
		int totalSum = 0;
		while (n > 0) {
			int d = n % 10;
			n = n / 10;
			totalSum += d * d;
		}
		return totalSum;
	}
	// 方法一：用 HashSet 检测循环
	public boolean isHappy1(int n) {
		Set<Integer> seen = new HashSet<>();
		//两种可能：最终会得到 1，最终会进入循环。
		while (n != 1 && !seen.contains(n)) {
			seen.add(n);
			n = getNext(n);
		}
		return n == 1;
	}
	//方法二：快慢指针法
	public boolean isHappy2(int n) {
		int slowRunner = n;
		int fastRunner = getNext(n);
		while(fastRunner!=1&&slowRunner!=fastRunner) {
			slowRunner = getNext(slowRunner);
			fastRunner = getNext(getNext(fastRunner));
		}
		return fastRunner==1;
	}
	//方法三：数学
	private static Set<Integer> cycleMembers =
	        new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
	public boolean isHappy3(int n) {
        while (n != 1 && !cycleMembers.contains(n)) {
            n = getNext(n);
        }
        return n == 1;
    }
}
